using System.Text.RegularExpressions;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Threading;
using UnityEngine;
using Cysharp.Threading.Tasks;
using Unity.Mathematics;
using UnityEngine.Networking;// using Newtonsoft.Json
using Newtonsoft.Json.Linq;
using System.IO;
using System.Linq;
using JeffreyLanters.WebRequests;
using System.Net;
using System.Text;
using EarthUtility;
using EarthGeospatial;
using Geometry;

namespace Cesium3DTilesSelection
{
    public class TilesetExternals
    {
        public IPrepareRendererResources pPrepareRendererResources;
    }
    struct LoadRecord
    {
        public Tile pTile;
        ///Lower priority values load sooner.
        public double priority;

        public static bool operator <(LoadRecord lhs, LoadRecord rhs)
        {
            return lhs.priority < rhs.priority;
        }
        public static bool operator >(LoadRecord lhs, LoadRecord rhs)
        {
            return lhs.priority > rhs.priority;
        }
    }

    class LoadResult
    {
        public TileContext pContext;
        public Tile pRootTile;
        public bool supportsRasterOverlays;

        public LoadResult(TileContext context, Tile rootTile, bool support = false)
        {
            this.pContext = context;
            this.pRootTile = rootTile;
            supportsRasterOverlays = support;
        }
    }


    public class Tileset
    {
        List<LoadRecord> _loadQueueHigh = new List<LoadRecord>();
        List<LoadRecord> _loadQueueMedium = new List<LoadRecord>();
        List<LoadRecord> _loadQueueLow = new List<LoadRecord>();
        private int _loadsInProgress; // TODO: does this need to be atomic?
        private Int64 _tileDataBytes;

        List<TileContext> _contexts = new List<TileContext>();
        public TilesetExternals externals { get; set; }
        //   CesiumAsync::AsyncSystem _asyncSystem;

        // per-tileset credit passed in explicitly by the user through
        // `TilesetOptions`
        //   std::optional<Credit> _userCredit;
        //  credits provided with the tileset from Cesium Ion
        //   List<Credit> _tilesetCredits;

        string _url;
        string _ionAssetID;
        string _ionAccessToken;
        bool _isRefreshingIonToken;

        TilesetOptions _options;

        Tile _pRootTile;

        internal ViewUpdateResult updateViewOffline(List<ViewState> frustums)
        {
            throw new NotImplementedException();
        }

        int _previousFrameNumber;
        ViewUpdateResult _updateResult = new ViewUpdateResult();

        LinkedList<Tile> _loadedTiles = new LinkedList<Tile>();

        public RasterOverlayCollection Overlays { get; set; }

        public bool SupportsRasterOverlays { get; set; }
        public TilesetOptions Options => _options;

        Geometry.Axis _gltfUpAxis;

        List<List<double>> _distancesStack = new List<List<double>>();
        int _nextDistancesVector;

        public Tileset()
        {
            this.Overlays = new RasterOverlayCollection(this);
        }
        public Tileset(TilesetExternals externals, string url, TilesetOptions options) : this()
        {
            this.externals = externals;
            Interlocked.Increment(ref _loadsInProgress);
            this._options = options;
        }

        public Tileset(TilesetExternals externals, string ionAssetID, string ionAccessToken, TilesetOptions options) : this()
        {
            this.externals = externals;
            string ionUrl = string.Format("https://api.cesium.com/v1/assets/{0}/endpoint?access_token={1}", ionAssetID, ionAccessToken);
            this._options = options;


            Interlocked.Increment(ref _loadsInProgress);
            _handleAssetResponse(ionUrl).Forget();
        }

        async UniTaskVoid _handleAssetResponse(string ionurl)
        {
            var json = await http.Get(ionurl);
            var jobj = JObject.Parse(json);
            string url = jobj["url"].ToString();
            string type = jobj["type"].ToString();
            string accessToken = jobj["accessToken"].ToString();
            if (type == "TERRAIN")
            {
                url += "layer.json";
            }
            else if (type != "3DTILES")
            {
                notifyTileDoneLoading(null);
                return;
            }
            var pContext = new TileContext();
            pContext.pTileset = this;
            pContext.baseUrl = url;
            pContext.requestHeaders["Authorization"] = string.Format("Bearer {0}", accessToken);
            pContext.failedTileCallback = _onIonTileFailed;
            _loadTilesetJson(pContext.baseUrl, pContext.requestHeaders, pContext).Forget();
        }

       public  void notifyTileStartLoading(Tile pTile)
        {
            Interlocked.Increment(ref _loadsInProgress);
            //   if (pTile) {
            //     CESIUM_TRACE_BEGIN_IN_TRACK(
            //         TileIdUtilities::createTileIdString(pTile->getTileID()).c_str());
            //   }
        }

        public void notifyTileDoneLoading(Tile pTile)
        {
            Interlocked.Decrement(ref _loadsInProgress);
            if (pTile)
            {
                this._tileDataBytes += pTile.computeByteSize();
            }
        }
        public void notifyTileUnloading(Tile pTile)
        {
            if (pTile)
            {
                this._tileDataBytes -= pTile.computeByteSize();
            }
        }


        FailedTileAction _onIonTileFailed(Tile failedTile)
        {
            return FailedTileAction.GiveUp;
        }

        async UniTaskVoid _loadTilesetJson(string url, Dictionary<string, string> header, TileContext pContext)
        {
            if (pContext == null)
            {
                pContext = new TileContext();
            }
            pContext.pTileset = this;

            var loadResult = await _handleTilesetResponse(url, header, pContext, false);
            this.SupportsRasterOverlays = loadResult.supportsRasterOverlays;
            this.addContext(loadResult.pContext);
            this._pRootTile = loadResult.pRootTile;
            this.notifyTileDoneLoading(null);
        }

        async UniTask<LoadResult> _handleTilesetResponse(string url, Dictionary<string, string> header, TileContext pContext, bool useWaterMask)
        {
            var request = await http.Get(url, null, header);
            var tileset = JObject.Parse(request);
            pContext.pTileset._gltfUpAxis = obtainGltfUpAxis(tileset);
            var pRootTile = new Tile();
            pRootTile.pContext = pContext;

            var formatIt = tileset["format"];
            bool supportsRasterOverlays = false;
            if (tileset.TryGetValue("root", out var rootjToken))
            {
                _createTile(pRootTile, rootjToken, double4x4.identity, TileRefine.Replace, pContext);
            }
            else if (formatIt.Value<string>() == "quantized-mesh-1.0")
            {
                _createTerrainTile(pRootTile, tileset, pContext, useWaterMask);
                supportsRasterOverlays = true;
            }

            return new LoadResult(pContext, pRootTile, supportsRasterOverlays);
        }

        internal void addContext(TileContext pNewTileContext)
        {
            _contexts.Add(pNewTileContext);
        }

        void _createTile(Tile tile, JToken tileJson, double4x4 parentTransform, TileRefine parentRefine, TileContext context)
        {
            if (tileJson.Type != JTokenType.Object)
            {
                return;
            }

            tile.pContext = context;

            double4x4? tileTransform = JsonHelpers.getTransformProperty(tileJson, "transform");
            double4x4 transform = math.mul(parentTransform, tileTransform.HasValue ? tileTransform.Value : double4x4.identity);
            tile.transform = transform;

            var contentIt = tileJson["content"];
            var childrenIt = tileJson["children"];

            if (contentIt != null && contentIt.Type == JTokenType.Object)
            {
                var uriIt = contentIt["uri"];
                if (uriIt != null || uriIt.Type != JTokenType.String)
                {
                    uriIt = contentIt["url"];
                }

                if (uriIt != null && uriIt.Type == JTokenType.String)
                {
                    tile.ID.id = uriIt.Value<string>();
                }

                BoundingVolume contentBoundingVolume = getBoundingVolumeProperty(contentIt, "boundingVolume");
                if (contentBoundingVolume)
                {
                    tile.contentBoundingVolume = BoundingVolume.transformBoundingVolume(transform, contentBoundingVolume);
                }
            }

            BoundingVolume boundingVolume = getBoundingVolumeProperty(tileJson, "boundingVolume");
            if (!boundingVolume)
            {
                Debug.LogError("Tile did not contain a boundingVolume");
                return;
            }

            double? geometricError = JsonHelpers.getScalarProperty(tileJson, "geometricError");
            if (!geometricError.HasValue)
            {
                Debug.LogError("Tile did not contain a geometricError");
                return;
            }

            tile.boundingVolume = BoundingVolume.transformBoundingVolume(transform, boundingVolume);
            double3 scale = new double3(
               math.length(transform[0]),
               math.length(transform[1]),
               math.length(transform[2]));
            double maxScaleComponent = math.max(scale.x, math.max(scale.y, scale.z));
            tile.geometricError = geometricError.Value * maxScaleComponent;

            BoundingVolume viewerRequestVolume = getBoundingVolumeProperty(tileJson, "viewerRequestVolume");
            if (viewerRequestVolume)
            {
                tile.viewerRequestVolume = BoundingVolume.transformBoundingVolume(transform, viewerRequestVolume);
            }

            var refineIt = tileJson["refine"];
            if (refineIt != null && refineIt.Type == JTokenType.String)
            {
                string refine = (string)refineIt;
                if (refine == "REPLACE")
                {
                    tile.refine = TileRefine.Replace;
                }
                else if (refine == "ADD")
                {
                    tile.refine = TileRefine.Add;
                }
                else
                {
                    Debug.LogError($"Tile contained an unknown refine value: {{refine}}");
                }
            }
            else
            {
                tile.refine = parentRefine;
            }

            if (childrenIt != null && childrenIt.Type == JTokenType.Array)
            {
                var size = childrenIt.Count();
                tile.createChildTiles(size);
                var childTiles = tile.children;
                for (int i = 0; i < size; ++i)
                {
                    var childJson = childrenIt[i];
                    Tile child = childTiles[i];
                    child.pParent = tile;
                    _createTile(child, childJson, transform, tile.refine, context);
                }
            }
        }

        private BoundingVolume getBoundingVolumeProperty(JToken tileJson, string key)
        {
            var bvIt = tileJson[key];
            if (bvIt == null)
            {
                return null;
            }

            var boxIt = bvIt["box"];
            if (boxIt != null && boxIt.Type == JTokenType.Array && boxIt.Count() >= 12)
            {
                for (int i = 0; i < 12; i++)
                {
                    if (boxIt[i].Type != JTokenType.Float)
                    {
                        return null;
                    }
                }
                return new OrientedBoundingBox(
                    new double3((double)boxIt[0], (double)boxIt[1], (double)boxIt[2]),
                    new double3x3(
                        (double)boxIt[3],
                        (double)boxIt[4],
                        (double)boxIt[5],
                        (double)boxIt[6],
                        (double)boxIt[7],
                        (double)boxIt[8],
                        (double)boxIt[9],
                        (double)boxIt[10],
                        (double)boxIt[11]));
            }

            var regionIt = bvIt["region"];
            if (regionIt != null && regionIt.Type == JTokenType.Array && regionIt.Count() >= 6)
            {
                for (int i = 0; i < 6; ++i)
                {
                    if (regionIt[i].Type != JTokenType.Float)
                    {
                        return null;
                    }
                }
                return new BoundingRegion(new GlobeRectangle(
                        (double)regionIt[0],
                        (double)regionIt[1],
                        (double)regionIt[2],
                        (double)regionIt[3]),
                        (double)regionIt[4],
                        (double)regionIt[5]);
            }

            var sphereIt = bvIt["sphere"];
            if (sphereIt != null && sphereIt.Type == JTokenType.Array && sphereIt.Count() >= 4)
            {
                for (int i = 0; i < 4; ++i)
                {
                    if (sphereIt[i].Type != JTokenType.Float)
                    {
                        return null;
                    }
                }
                return new BoundingSphere(
                    new double3((double)sphereIt[0], (double)sphereIt[1], (double)sphereIt[2]), (double)sphereIt[3]);
            }

            return null;
        }

        void _createTerrainTile(Tile tile, JObject layerJson, TileContext context, bool useWaterMask)
        {
            context.requestHeaders["Accept"] = "application/vnd.quantized-mesh,application/octet-stream;q=0.9,*/*;q=0.01";

            var tilesetVersionIt = layerJson["version"];
            context.version = tilesetVersionIt.Value<string>();
            var bounds = JsonHelpers.getDoubles(layerJson, "bounds");
            var projectionString = JsonHelpers.getStringOrDefault(layerJson, "projection", "EPSG:4326");

            Projection projection = new Projection();
            var quadtreeRectangleGlobe = new GlobeRectangle(0.0, 0.0, 0.0, 0.0);
            var quadtreeRectangleProjected = new Rectangle(0.0, 0.0, 0.0, 0.0);
            int quadtreeXTiles = 0;
            if (projectionString == "EPSG:4326")
            {
                GeographicProjection geographic = new GeographicProjection();
                projection.useProjection(geographic);
                quadtreeRectangleGlobe = bounds.Count >= 4 ? GlobeRectangle.fromDegrees(
                                 bounds[0],
                                 bounds[1],
                                 bounds[2],
                                 bounds[3]) :
                                 GeographicProjection.MAXIMUM_GLOBE_RECTANGLE;
                quadtreeRectangleProjected = geographic.project(quadtreeRectangleGlobe);
                quadtreeXTiles = 2;
            }
            else if (projectionString == "EPSG:3857")
            {
                WebMercatorProjection webMercator = new WebMercatorProjection();
                projection.useProjection(webMercator);
                quadtreeRectangleGlobe = bounds.Count >= 4 ? GlobeRectangle.fromDegrees(
                                    bounds[0],
                                    bounds[1],
                                    bounds[2],
                                    bounds[3])
                              : WebMercatorProjection.MAXIMUM_GLOBE_RECTANGLE;
                quadtreeRectangleProjected = webMercator.project(quadtreeRectangleGlobe);
                quadtreeXTiles = 1;
            }
            else
            {
                Debug.Log($"Tileset contained an unknown projection value:{projectionString}");
            }

            QuadtreeTilingScheme tilingScheme = new QuadtreeTilingScheme(quadtreeRectangleProjected, quadtreeXTiles, 1);
            var urls = JsonHelpers.getStrings(layerJson, "tiles");
            int maxZoom = JsonHelpers.getUint32OrDefault(layerJson, "maxzoom", 30);

            context.implicitContext = new ImplicitTilingContext
            {
                tileTemplateUrls = urls,
                tilingScheme = tilingScheme,
                projection = projection,
                availability = new QuadtreeTileAvailability(tilingScheme, maxZoom)
            };

            List<string> extensions = JsonHelpers.getStrings(layerJson, "extensions");
            List<string> knownExtensions = new List<string> { "octvertexnormals", "metadata" };
            if (useWaterMask)
            {
                knownExtensions.Add("watermask");
            }

            string extensionsToRequest = createExtensionsQueryParameter(knownExtensions, extensions);
            if (extensionsToRequest.Any())
            {
                for (var i = 0; i < context.implicitContext.tileTemplateUrls.Count; i++)
                {
                    var url = context.implicitContext.tileTemplateUrls[i];
                    context.implicitContext.tileTemplateUrls[i] = UriOpr.addQuery(url, "extensions", extensionsToRequest);
                }
            }
            tile.pContext = context;
            tile.boundingVolume = createDefaultLooseEarthBoundingVolume(quadtreeRectangleGlobe);
            tile.geometricError = 999999999.0;
            tile.createChildTiles(quadtreeXTiles);
            for (var i = 0; i < quadtreeXTiles; i++)
            {
                var childTile = tile.children[i];
                QuadtreeTileID id = new QuadtreeTileID(0, i, 0);
                childTile.pContext = context;
                childTile.pParent = tile;
                childTile.ID.quadtreeID = id;
                GlobeRectangle childGlobeRectangle = Projection.unprojectRectangleSimple(projection, tilingScheme.tileToRectangle(id));
                childTile.boundingVolume = createDefaultLooseEarthBoundingVolume(childGlobeRectangle);
                childTile.geometricError = 8.0 * Ellipsoid.calcQuadtreeMaxGeometricError(Ellipsoid.WGS84) * childGlobeRectangle.computeWidth();
            }

        }



        public static BoundingVolume createDefaultLooseEarthBoundingVolume(GlobeRectangle globeRectangle)
        {
            var boundingVolume = new BoundingVolume(new BoundingRegionWithLooseFittingHeights(new BoundingRegion(globeRectangle, -1000.0, -9000.0)));
            boundingVolume.pLooseRegion = new BoundingRegionWithLooseFittingHeights(new BoundingRegion(globeRectangle, -1000.0, -9000.0));
            return boundingVolume;
        }

        /**
* @brief Creates the query parameter string for the extensions in the given
* list.
*
* This will check for the presence of all known extensions in the given list,
* and create a string that can be appended as the value of the `extensions`
* query parameter to the request URL.
*
* @param extensions The layer JSON
* @return The extensions (possibly the empty string)
*/
        public static string createExtensionsQueryParameter(
            List<string> knownExtensions,
            List<string> extensions)
        {

            string extensionsToRequest = "";
            foreach (var extension in knownExtensions)
            {
                if (!string.IsNullOrEmpty(extensionsToRequest))
                {
                    extensionsToRequest += "-";
                }
                extensionsToRequest += extension;
            }
            return extensionsToRequest;
        }

        public Axis getGltfUpAxis()
        {
            return _gltfUpAxis;
        }

        public async UniTask<string> requestTileContent(Tile tile)
        {
            string url = getResolvedContentUrl(tile);
            return url;
        }

        public string getResolvedContentUrl(Tile tile)
        {
            if (!tile.ID.quadtreeID.HasValue) return null;
            var tempUrl = tile.pContext.implicitContext.tileTemplateUrls.First();
            var matchStr = Regex.Replace(tempUrl, @"\{\w+\}", placeholder =>
             {
                 if (placeholder.Value == "{level}" || placeholder.Value == "{z}")
                     return tile.ID.quadtreeID.Value.level + "";
                 if (placeholder.Value == "{x}")
                     return tile.ID.quadtreeID.Value.x + "";
                 if (placeholder.Value == "{y}")
                     return tile.ID.quadtreeID.Value.y + "";
                 if (placeholder.Value == "{version}")
                     return tile.pContext.version;
                 return placeholder.Value;
             });
            // tile.pContext.baseUrl
            return new Uri(new Uri(tile.pContext.baseUrl), matchStr).ToString();
        }

        /**
   * @brief Obtains the up-axis that should be used for glTF content of the
   * tileset.
   *
   * If the given tileset JSON does not contain an `asset.gltfUpAxis` string
   * property, then the default value of CesiumGeometry::Axis::Y is returned.
   *
   * Otherwise, a warning is printed, saying that the `gltfUpAxis` property is
   * not strictly compliant to the 3D tiles standard, and the return value
   * will depend on the string value of this property, which may be "X", "Y", or
   * "Z", case-insensitively, causing CesiumGeometry::Axis::X,
   * CesiumGeometry::Axis::Y, or CesiumGeometry::Axis::Z to be returned,
   * respectively.
   *
   * @param tileset The tileset JSON
   * @return The up-axis to use for glTF content
   */
        public Geometry.Axis obtainGltfUpAxis(JObject tileset)
        {
            if (!tileset.ContainsKey("asset"))
            {
                return Geometry.Axis.Y;
            }
            JToken asset = tileset["asset"];
            var gltfUpAxisString = asset.Value<string>("gltfUpAxis");
            if (string.IsNullOrEmpty(gltfUpAxisString))
            {
                return Geometry.Axis.Y;
            }

            Debug.LogWarning(@"The tileset contains a gltfUpAxis property.\n
              This property is not part of the specification.\n 
              All glTF content should use the Y-axis as the up-axis.");


            if (gltfUpAxisString == "X" || gltfUpAxisString == "x")
            {
                return Geometry.Axis.X;
            }
            if (gltfUpAxisString == "Y" || gltfUpAxisString == "y")
            {
                return Geometry.Axis.Y;
            }
            if (gltfUpAxisString == "Z" || gltfUpAxisString == "z")
            {
                return Geometry.Axis.Z;
            }
            Debug.LogWarning(string.Format("Unknown gltfUpAxis: {0}, using default (Y)", gltfUpAxisString));
            return Geometry.Axis.Y;
        }
        public ViewUpdateResult updateView(List<ViewState> frustums)
        {
            int previousFrameNumber = this._previousFrameNumber;
            int currentFrameNumber = previousFrameNumber + 1;
            ViewUpdateResult result = _updateResult;
            // result.tilesLoading = 0;
            result.tilesToRenderThisFrame.Clear();
            // result.newTilesToRenderThisFrame.clear();
            result.tilesToNoLongerRenderThisFrame.Clear();
            result.tilesVisited = 0;
            result.culledTilesVisited = 0;
            result.tilesCulled = 0;
            result.maxDepthVisited = 0;

            Tile pRootTile = this._pRootTile;
            if (pRootTile == null) return result;

            if (!this.SupportsRasterOverlays && this.Overlays.Count > 0)
            {
                Debug.LogWarning("Only quantized-mesh terrain tilesets currently support overlays.");
            }
            this._loadQueueHigh.Clear();
            this._loadQueueMedium.Clear();
            this._loadQueueLow.Clear();

            //  = new List<double>(frustums.Count);
            //处理fog
            List<double> fogDensities = frustums.Select(x => computeFogDensity(x)).ToList();
            FrameState frameState = new FrameState();
            frameState.frustums = frustums;
            frameState.fogDensities = fogDensities;
            frameState.lastFrameNumber = previousFrameNumber;
            frameState.currentFrameNumber = currentFrameNumber;
            if (frustums.Count > 0)
            {
                this._visitTileIfNeeded(frameState, 0, false, pRootTile, result);
            }
            else
            {
                return new ViewUpdateResult();
            }
            result.tilesLoadingLowPriority = _loadQueueLow.Count;
            result.tilesLoadingMediumPriority = _loadQueueMedium.Count;
            result.tilesLoadingHighPriority = _loadQueueHigh.Count;

            this._unloadCachedTiles();
            this._processLoadQueue();

            this._previousFrameNumber = currentFrameNumber;
            return result;
        }

        private void _processLoadQueue()
        {
            this.processQueue(this._loadQueueHigh, ref this._loadsInProgress, this._options.maximumSimultaneousTileLoads);
            this.processQueue(this._loadQueueMedium, ref this._loadsInProgress, this._options.maximumSimultaneousTileLoads);
            this.processQueue(this._loadQueueLow, ref this._loadsInProgress, this._options.maximumSimultaneousTileLoads);
        }

        private void processQueue(List<LoadRecord> queue, ref int loadsInProgress, uint maximumLoadsInProgress)
        {
            if (loadsInProgress >= maximumLoadsInProgress) return;
            queue.Sort((x, y) => x < y ? -1 : 1);
            foreach (var record in queue)
            {
                record.pTile.loadContent();
                if (loadsInProgress >= maximumLoadsInProgress)
                {
                    break;
                }
            }
        }

        public static implicit operator bool(Tileset foo)
        {
            return foo == null ? false : true;
        }


        Int64 getTotalDataBytes()
        {
            throw new NotImplementedException();
            Int64 bytes = this._tileDataBytes;
            foreach (var item in Overlays)
            {

            }
        }
        void _unloadCachedTiles()
        {
            Int64 maxBytes = this.Options.maximumCachedBytes;
            Tile pTile = this._loadedTiles.First();
            // while (getTotalDataBytes()>maxBytes)
            // {
            //      if(pTile==null||pTile==this._pRootTile){
            //          break;
            //      }
            //      foreach (var pNext in this._loadedTiles)
            //      {
            //           bool removed = pNext.unloadContent();
            //           if(removed){
            //               this._loadedTiles.Remove(pNext);
            //           }
            //      }
            // }
        }

        private TraversalDetails _visitTileIfNeeded(FrameState frameState, int depth, bool ancestorMeetsSse, Tile tile, ViewUpdateResult result)
        {
            tile.update(frameState.lastFrameNumber, frameState.currentFrameNumber);
            this._markTileVisited(tile);
            if (!tile.pTileset)
            {
                return new TraversalDetails();
            }
            bool shouldVisit = true;
            bool culled = false;

            //   foreach (var item in _options.excluders)
            //   {
            //       for
            //   }

            var frustums = frameState.frustums;
            var fogDensities = frameState.fogDensities;
            BoundingVolume boundingVolume = tile.boundingVolume;

            bool none_of = !frustums.Any(x => isVisibleFromCamera(x, boundingVolume, _options.renderTilesUnderCamera));
            if (none_of)
            {
                culled = true;
                if (this._options.enableFrustumCulling)
                {
                    shouldVisit = false;
                }
            }
            if (this._nextDistancesVector >= this._distancesStack.Count)
            {
                this._distancesStack.Add(null);
            }

            this._distancesStack[_nextDistancesVector] = frustums.Select(x => x.computeDistanceSquaredToBoundingVolume(boundingVolume)).ToList();
            var distances = this._distancesStack[_nextDistancesVector];
            if (shouldVisit)
            {
                bool isFogCulled = true;

                for (int i = 0; i < frustums.Count; ++i)
                {
                    double distance = distances[i];
                    double fogDensity = fogDensities[i];

                    if (isVisibleInFog(distance, fogDensity))
                    {
                        isFogCulled = false;
                        break;
                    }
                }

                if (isFogCulled)
                {
                    // this tile is occluded by fog so it is a culled tile
                    culled = true;
                    if (this._options.enableFogCulling)
                    {
                        // fog culling is enabled so we shouldn't visit this tile
                        shouldVisit = false;
                    }
                }
            }
            if (!shouldVisit)
            {
                markTileAndChildrenNonRendered(frameState.lastFrameNumber, tile, result);
                tile.lastSelectionState = new TileSelectionState(frameState.currentFrameNumber, TileSelectionState.Result.Culled);
                if (this._options.preloadSiblings)
                {
                    addTileToLoadQueue(this._loadQueueLow, frustums, tile, distances);
                }
                result.tilesCulled++;
                return new TraversalDetails();
            }

            return this._visitTile(frameState, depth, ancestorMeetsSse, tile, distances, culled, result);
        }

        private bool isVisibleInFog(double distance, double fogDensity)
        {
            return true;
        }

        private TraversalDetails _visitTile(FrameState frameState, int depth, bool ancestorMeetsSse, Tile tile, List<double> distances, bool culled, ViewUpdateResult result)
        {
            result.tilesVisited++;
            result.maxDepthVisited = math.max(result.maxDepthVisited, depth);
            if (culled)
            {
                result.culledTilesVisited++;
            }
            if (isLeaf(tile))
            {
                return _renderLeaf(frameState, tile, distances, result);
            }
            bool unconditionallyRefine = tile.getUnconditionallyRefine();
            bool meetsSse = _meetsSse(frameState.frustums, tile, distances, culled);
            bool waitingForChildren = _queueLoadOfChildrenRequiredForRefinement(frameState, tile, distances);
            if (!unconditionallyRefine && (meetsSse || ancestorMeetsSse || waitingForChildren))
            {
                // This tile (or an ancestor) is the one we want to render this frame, but
                // we'll do different things depending on the state of this tile and on what
                // we did _last_ frame.

                // We can render it if _any_ of the following are true:
                // 1. We rendered it (or kicked it) last frame.
                // 2. This tile was culled last frame, or it wasn't even visited because an
                // ancestor was culled.
                // 3. The tile is done loading and ready to render.
                //
                // Note that even if we decide to render a tile here, it may later get
                // "kicked" in favor of an ancestor.
                TileSelectionState lastFrameSelectionState = tile.lastSelectionState;
                bool renderThisTile = shouldRenderThisTile(tile, lastFrameSelectionState, frameState.lastFrameNumber);
                if (renderThisTile)
                {
                    // Only load this tile if it (not just an ancestor) meets the SSE.
                    if (meetsSse && !ancestorMeetsSse)
                    {
                        addTileToLoadQueue(this._loadQueueMedium, frameState.frustums, tile, distances);
                    }
                    return _renderInnerTile(frameState, tile, result);
                }

                // Otherwise, we can't render this tile (or blank space where it would be)
                // because doing so would cause detail to disappear that was visible last
                // frame. Instead, keep rendering any still-visible descendants that were
                // rendered last frame and render nothing for newly-visible descendants.
                // E.g. if we were rendering level 15 last frame but this frame we want
                // level 14 and the closest renderable level <= 14 is 0, rendering level
                // zero would be pretty jarring so instead we keep rendering level 15 even
                // though its SSE is better than required. So fall through to continue
                // traversal...
                ancestorMeetsSse = true;

                // Load this blocker tile with high priority, but only if this tile (not
                // just an ancestor) meets the SSE.
                if (meetsSse)
                {
                    addTileToLoadQueue(this._loadQueueHigh, frameState.frustums, tile, distances);
                }
            }
            // Refine!
            bool queuedForLoad = _loadAndRenderAdditiveRefinedTile(frameState, tile, result, distances);

            int firstRenderedDescendantIndex = result.tilesToRenderThisFrame.Count;
            int loadIndexLow = this._loadQueueLow.Count;
            int loadIndexMedium = this._loadQueueMedium.Count;
            int loadIndexHigh = this._loadQueueHigh.Count;

            TraversalDetails traversalDetails = this._visitVisibleChildrenNearToFar(frameState, depth, ancestorMeetsSse, tile, result);

            bool descendantTilesAdded = firstRenderedDescendantIndex != result.tilesToRenderThisFrame.Count;
            if (!descendantTilesAdded)
            {
                // No descendant tiles were added to the render list by the function above,
                // meaning they were all culled even though this tile was deemed visible.
                // That's pretty common.
                return _refineToNothing(frameState, tile, result, traversalDetails.allAreRenderable);
            }

            // At least one descendant tile was added to the render list.
            // The traversalDetails tell us what happened while visiting the children.
            if (!traversalDetails.allAreRenderable &&
                !traversalDetails.anyWereRenderedLastFrame)
            {
                // Some of our descendants aren't ready to render yet, and none were
                // rendered last frame, so kick them all out of the render list and render
                // this tile instead. Continue to load them though!
                queuedForLoad = _kickDescendantsAndRenderTile(
                    frameState,
                    tile,
                    result,
                    traversalDetails,
                    firstRenderedDescendantIndex,
                    loadIndexLow,
                    loadIndexMedium,
                    loadIndexHigh,
                    queuedForLoad,
                    distances);
            }
            else
            {
                if (tile.refine != TileRefine.Add)
                {
                    markTileNonRendered(frameState.lastFrameNumber, tile, result);
                }
                tile.lastSelectionState = new TileSelectionState(frameState.currentFrameNumber, TileSelectionState.Result.Refined);
            }

            if (this._options.preloadAncestors && !queuedForLoad)
            {
                addTileToLoadQueue(this._loadQueueLow, frameState.frustums, tile, distances);
            }

            return traversalDetails;
        }

        private TraversalDetails _visitVisibleChildrenNearToFar(FrameState frameState, int depth, bool ancestorMeetsSse, Tile tile, ViewUpdateResult result)
        {
            TraversalDetails traversalDetails = new TraversalDetails();
            // TODO: actually visit near-to-far, rather than in order of occurrence.
            var children = tile.children;
            foreach (Tile child in children)
            {
                TraversalDetails childTraversal = this._visitTileIfNeeded(frameState, depth + 1, ancestorMeetsSse, child, result);
                traversalDetails.allAreRenderable &= childTraversal.allAreRenderable;
                traversalDetails.anyWereRenderedLastFrame |= childTraversal.anyWereRenderedLastFrame;
                traversalDetails.notYetRenderableCount += childTraversal.notYetRenderableCount;
            }

            return traversalDetails;
        }

        private bool _kickDescendantsAndRenderTile(FrameState frameState, Tile tile, ViewUpdateResult result, TraversalDetails traversalDetails, int firstRenderedDescendantIndex, int loadIndexLow, int loadIndexMedium, int loadIndexHigh, bool queuedForLoad, List<double> distances)
        {
            TileSelectionState lastFrameSelectionState = tile.lastSelectionState;
            var renderList = result.tilesToRenderThisFrame;
            // Mark the rendered descendants and their ancestors - up to this tile - as
            // kicked.
            for (int i = firstRenderedDescendantIndex; i < renderList.Count; ++i)
            {
                Tile pWorkTile = renderList[i];
                while (pWorkTile != null && !pWorkTile.lastSelectionState.wasKicked(frameState.currentFrameNumber) && pWorkTile != tile)
                {
                    pWorkTile.lastSelectionState.kick();
                    pWorkTile = pWorkTile.pParent;
                }
            }
            // Remove all descendants from the render list and add this tile.
            renderList.RemoveAt(firstRenderedDescendantIndex);

            if (tile.refine != TileRefine.Add)
            {
                renderList.Add(tile);
            }

            tile.lastSelectionState = (new TileSelectionState(frameState.currentFrameNumber, TileSelectionState.Result.Rendered));

            // If we're waiting on heaps of descendants, the above will take too long. So
            // in that case, load this tile INSTEAD of loading any of the descendants, and
            // tell the up-level we're only waiting on this tile. Keep doing this until we
            // actually manage to render this tile.
            bool wasRenderedLastFrame = lastFrameSelectionState.getResult(frameState.lastFrameNumber) == TileSelectionState.Result.Rendered;
            bool wasReallyRenderedLastFrame = wasRenderedLastFrame && tile.isRenderable();

            if (!wasReallyRenderedLastFrame && traversalDetails.notYetRenderableCount > this._options.loadingDescendantLimit)
            {
                // Remove all descendants from the load queues.
                this._loadQueueLow.RemoveAt(loadIndexLow);
                this._loadQueueMedium.RemoveAt(loadIndexMedium);
                this._loadQueueHigh.RemoveAt(loadIndexHigh);

                if (!queuedForLoad)
                {
                    addTileToLoadQueue(this._loadQueueMedium, frameState.frustums, tile, distances);
                }
                traversalDetails.notYetRenderableCount = tile.isRenderable() ? 0 : 1;
                queuedForLoad = true;
            }

            traversalDetails.allAreRenderable = tile.isRenderable();
            traversalDetails.anyWereRenderedLastFrame = wasRenderedLastFrame;

            return queuedForLoad;
        }

        private TraversalDetails _refineToNothing(FrameState frameState, Tile tile, ViewUpdateResult result, bool allAreRenderable)
        {
            throw new NotImplementedException();
        }

        private bool _loadAndRenderAdditiveRefinedTile(FrameState frameState, Tile tile, ViewUpdateResult result, List<double> distances)
        {
            if (tile.refine == TileRefine.Add)
            {
                result.tilesToRenderThisFrame.Add(tile);
                addTileToLoadQueue(this._loadQueueMedium, frameState.frustums, tile, distances);
                return true;
            }

            return false;
        }

        private TraversalDetails _renderInnerTile(FrameState frameState, Tile tile, ViewUpdateResult result)
        {
            TileSelectionState lastFrameSelectionState = tile.lastSelectionState;

            markChildrenNonRendered(frameState.lastFrameNumber, tile, result);
            tile.lastSelectionState = new TileSelectionState(frameState.currentFrameNumber, TileSelectionState.Result.Rendered);
            result.tilesToRenderThisFrame.Add(tile);

            TraversalDetails traversalDetails = new TraversalDetails();
            traversalDetails.allAreRenderable = tile.isRenderable();
            traversalDetails.anyWereRenderedLastFrame =
                lastFrameSelectionState.getResult(frameState.lastFrameNumber) == TileSelectionState.Result.Rendered;
            traversalDetails.notYetRenderableCount =
                traversalDetails.allAreRenderable ? 0 : 1;

            return traversalDetails;
        }

        private void markChildrenNonRendered(int lastFrameNumber, Tile tile, ViewUpdateResult result)
        {
            TileSelectionState.Result lastResult = tile.lastSelectionState.getResult(lastFrameNumber);
            markChildrenNonRendered(lastFrameNumber, lastResult, tile, result);
        }

        private bool shouldRenderThisTile(Tile tile, TileSelectionState lastFrameSelectionState, int lastFrameNumber)
        {
            TileSelectionState.Result originalResult = lastFrameSelectionState.getOriginalResult(lastFrameNumber);
            if (originalResult == TileSelectionState.Result.Rendered)
            {
                return true;
            }
            if (originalResult == TileSelectionState.Result.Culled ||
                originalResult == TileSelectionState.Result.None)
            {
                return true;
            }

            // Tile::isRenderable is actually a pretty complex operation, so only do
            // it when absolutely necessary
            if (tile.isRenderable())
            {
                return true;
            }
            return false;
        }

        private bool _queueLoadOfChildrenRequiredForRefinement(FrameState frameState, Tile tile, List<double> distances)
        {
            if (!this._options.forbidHoles)
            {
                return false;
            }
            // If we're forbidding holes, don't refine if any children are still loading.
            var children = tile.children;
            bool waitingForChildren = false;
            foreach (Tile child in children)
            {
                if (!child.isRenderable() && !child.isExternalTileset())
                {
                    waitingForChildren = true;

                    // While we are waiting for the child to load, we need to push along the
                    // tile and raster loading by continuing to update it.
                    child.update(frameState.lastFrameNumber, frameState.currentFrameNumber);
                    this._markTileVisited(child);

                    // We're using the distance to the parent tile to compute the load
                    // priority. This is fine because the relative priority of the children is
                    // irrelevant; we can't display any of them until all are loaded, anyway.
                    addTileToLoadQueue(this._loadQueueMedium, frameState.frustums, child, distances);
                }
            }
            return waitingForChildren;
        }

        private bool _meetsSse(List<ViewState> frustums, Tile tile, List<double> distances, bool culled)
        {
            double largestSse = 0.0;
            for (var i = 0; i < frustums.Count && i < distances.Count; i++)
            {
                ViewState frustum = frustums[i];
                double distance = distances[i];
                double sse = frustum.computeScreenSpaceError(tile.geometricError, distance);
                if (sse > largestSse)
                {
                    largestSse = sse;
                }

            }
            return culled ? (!this._options.enforceCulledScreenSpaceError || largestSse < this._options.culledScreenSpaceError) : largestSse < this._options.maximumScreenSpaceError;
        }

        private TraversalDetails _renderLeaf(FrameState frameState, Tile tile, List<double> distances, ViewUpdateResult result)
        {
            TileSelectionState lastFrameSelectionState = tile.lastSelectionState;
            tile.lastSelectionState = new TileSelectionState(frameState.currentFrameNumber, TileSelectionState.Result.Rendered);
            result.tilesToRenderThisFrame.Add(tile);
            addTileToLoadQueue(this._loadQueueMedium, frameState.frustums, tile, distances);
            TraversalDetails traversalDetails = new TraversalDetails();
            traversalDetails.allAreRenderable = tile.isRenderable();
            traversalDetails.anyWereRenderedLastFrame = lastFrameSelectionState.getResult(frameState.lastFrameNumber) == TileSelectionState.Result.Rendered;
            traversalDetails.notYetRenderableCount = traversalDetails.allAreRenderable ? 0 : 1;
            return traversalDetails;
        }

        private bool isLeaf(Tile tile)
        {
            return !tile.children.Any();
        }

        private void addTileToLoadQueue(List<LoadRecord> loadQueue, List<ViewState> frustums, Tile tile, List<double> distances)
        {
            if (tile.state == Tile.LoadState.Unloaded || anyRasterOverlaysNeedLoading(tile))
            {
                double3 boundingVolumeCenter = BoundingVolume.getBoundingVolumeCenter(tile.boundingVolume);
                double highestLoadPriority = double.MaxValue;
                for (var i = 0; i < frustums.Count && i < distances.Count; i++)
                {
                    ViewState frustum = frustums[i];
                    double distance = distances[i];
                    double3 tileDirection = boundingVolumeCenter - frustum.getPosition();
                    double magnitude = math.length(tileDirection);
                    if (magnitude >= Mathd.EPSILON5)
                    {
                        tileDirection /= magnitude;
                        double loadPriority = (1 - math.dot(tileDirection, frustum.getDirection())) * distance;
                        if (loadPriority < highestLoadPriority)
                        {
                            highestLoadPriority = loadPriority;
                        }
                    }
                }
                loadQueue.Add(new LoadRecord { pTile = tile, priority = highestLoadPriority });
            }
        }

        static bool anyRasterOverlaysNeedLoading(Tile tile)
        {
            foreach (var mapped in tile.rasterTiles)
            {
                RasterOverlayTile pLoading = mapped.pLoadingTile;
                if (pLoading && pLoading.State == RasterOverlayTile.LoadState.Unloaded)
                {
                    return true;
                }
            }
            return false;
        }

        public static void markTileAndChildrenNonRendered(int lastFrameNumber, Tile tile, ViewUpdateResult result)
        {
            TileSelectionState.Result lastResult = tile.lastSelectionState.getResult(lastFrameNumber);
            markTileNonRendered(lastResult, tile, result);
            markChildrenNonRendered(lastFrameNumber, lastResult, tile, result);
        }

        private static void markChildrenNonRendered(int lastFrameNumber, TileSelectionState.Result lastResult, Tile tile, ViewUpdateResult result)
        {
            if (lastResult == TileSelectionState.Result.Refined)
            {
                foreach (Tile child in tile.children)
                {
                    TileSelectionState.Result childLastResult = child.lastSelectionState.getResult(lastFrameNumber);
                    markTileNonRendered(childLastResult, child, result);
                    markChildrenNonRendered(lastFrameNumber, childLastResult, child, result);
                }
            }
        }

        private static void markTileNonRendered(TileSelectionState.Result lastResult, Tile tile, ViewUpdateResult result)
        {
            if (lastResult == TileSelectionState.Result.Rendered)
            {
                result.tilesToNoLongerRenderThisFrame.Add(tile);
            }
        }

        private static void markTileNonRendered(int lastFrameNumber, Tile tile, ViewUpdateResult result)
        {
            TileSelectionState.Result lastResult = tile.lastSelectionState.getResult(lastFrameNumber);
            markTileNonRendered(lastResult, tile, result);
        }

        static bool isVisibleFromCamera(ViewState viewState, BoundingVolume boundingVolume, bool forceRenderTilesUnderCamera)
        {
            if (viewState.isBoundingVolumeVisible(boundingVolume))
            {
                return true;
            }
            if (!forceRenderTilesUnderCamera)
            {
                return false;
            }

            Cartographic? position = viewState.getPositionCartographic();

            // TODO: it would be better to test a line pointing down (and up?) from the
            // camera against the bounding volume itself, rather than transforming the
            // bounding volume to a region.
            GlobeRectangle pRectangle = Impl.obtainGlobeRectangle(boundingVolume);
            if (position.HasValue && pRectangle)
            {
                return pRectangle.contains(position.Value);
            }
            return false;
        }


        private void _markTileVisited(Tile tile)
        {
            this._loadedTiles.AddLast(tile);
        }

        public double computeFogDensity(ViewState v)
        {
            return 1;
        }


    }

    /**
     * @brief The result of traversing one branch of the tile hierarchy.
     *
     * Instances of this structure are created by the `_visit...` functions,
     * and summarize the information that was gathered during the traversal
     * of the respective branch, so that this information can be used by
     * the parent to decide on the further traversal process.
     */
    public class TraversalDetails
    {
        /**
         * @brief Whether all selected tiles in this tile's subtree are renderable.
         *
         * This is `true` if all selected (i.e. not culled or refined) tiles in this
         * tile's subtree are renderable. If the subtree is renderable, we'll render
         * it; no drama.
         */
        public bool allAreRenderable = true;

        /**
         * @brief Whether any tile in this tile's subtree was rendered in the last
         * frame.
         *
         * This is `true` if any tiles in this tile's subtree were rendered last
         * frame. If any were, we must render the subtree rather than this tile,
         * because rendering this tile would cause detail to vanish that was visible
         * last frame, and that's no good.
         */
        public bool anyWereRenderedLastFrame = false;

        /**
         * @brief The number of selected tiles in this tile's subtree that are not
         * yet renderable.
         *
         * Counts the number of selected tiles in this tile's subtree that are
         * not yet ready to be rendered because they need more loading. Note that
         * this value will _not_ necessarily be zero when
         * `allAreRenderable` is `true`, for subtle reasons.
         * When `allAreRenderable` and `anyWereRenderedLastFrame` are both `false`,
         * we will render this tile instead of any tiles in its subtree and the
         * `allAreRenderable` value for this tile will reflect only whether _this_
         * tile is renderable. The `notYetRenderableCount` value, however, will
         * still reflect the total number of tiles that we are waiting on, including
         * the ones that we're not rendering. `notYetRenderableCount` is only reset
         * when a subtree is removed from the render queue because the
         * `notYetRenderableCount` exceeds the
         * {@link TilesetOptions::loadingDescendantLimit}.
         */
        public int notYetRenderableCount = 0;
    }

}